package DataStr.homework04.h2;

public class MergeSort {
    public static void MergeSort(int[]a,int left,int right){
        //归并排序的递归函数
        if(left<right) {
            int mid = (left + right) / 2;//计算中间位置
            MergeSort(a, left, mid);//排序左边数组
            MergeSort(a, mid + 1, right);//排序右边数组
            merge(a, left, mid, right);
        }
    }
    public static void merge(int[]arr,int left,int mid,int right){
        //合并两个有序数组方法
        int n1=mid-left+1;//左边子数组长度
        int n2=right-mid;//右边子数组长度
        //创建两个数组用来存储左右数组元素
        int[]leftArray=new int[n1];
        int[]rightArray=new int[n2];
        //将arr中的左右元素复制过去
        System.arraycopy(arr,left,leftArray,0,n1);
        System.arraycopy(arr,mid+1,rightArray,0,n2);
        //接下来合并两个子数组
        int i=0,j=0,k=left;
        while(i<n1&&j<n2){
            if(leftArray[i]<=rightArray[j]){
                arr[k++]=leftArray[i++];
            }else{
                arr[k++]=rightArray[j++];
            }
        }
        //当循环结束时，还有一个数组有剩余元素，将剩下的一一合并到arr中
        while(i<n1){
            arr[k++]=leftArray[i++];
        }
        while(j<n2){
            arr[k++]=rightArray[j++];
        }
    }
    public static void main(String[]args){
        int[] arr = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.print("归并排序前的数组:");
        for(int num:arr){
            System.out.print(num+" ");
        }
        System.out.println();
        //递归并调用数据
        MergeSort(arr,0,arr.length-1);
        System.out.print("归并排序后的数组:");
        for(int num:arr){
            System.out.print(num+" ");
        }
    }
}
